package com.sgj.day2;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Guoji Shen
 * @Date: 2021/7/29 9:30
 */
public class TwoSum {
    /**
     * 根据 nums 数组里的两数的和（不能为重复的值）等于 target ，返回这两个数在 nums 数组里的下标，没有则返回空
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{2, 7, 11, 15};
        int target = 9;

        System.out.println("======================暴力算法==========================");
        // 暴力算法
        int[] myIndex = twoSum1(nums, target);
        for (int index : myIndex) {
            System.out.println(index);
        }

        System.out.println("======================哈希算法==========================");
        // 哈希算法
        int[] myIndex2 = twoSum2(nums, target);
        for (int index : myIndex2) {
            System.out.println(index);
        }
    }

    /**
     * 暴力算法
     * 通过双重循环便利数组种所有元素的两两组合，当出现符合的和时返回两个元素的下标
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (target - nums[i] == nums[j]) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    /**
     * 哈希算法
     * 通过 hashMap key不能重复的机制，只循环一次就可以返回两个下标
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            // 举例 7 = 9 - 2，若 map 没有 7，则把 2 存入 key，下标存入 value
            int partnerNumber = target - nums[i];
            if (map.containsKey(partnerNumber)) {
                // 此时进来 map{key: 2, value: 0}，所以直接返回 0 , 1
                return new int[]{map.get(partnerNumber), i};
            }
            map.put(nums[i], i);
        }

        return null;
    }
}